int n,m,s,t,x,y,z;
const int MAXN=5010,MAXM=60010;
const int inf=1000000000;

struct graph
{
	int a[MAXN],b[MAXM],c[MAXM],d[MAXM],p,h[MAXN],dd[MAXN],ll,rr;
	void clear()
	{
		memset(a,0,sizeof a);
		p=1;
	}
	void addedge(int x,int y,int z)
	{
		c[++p]=a[x]; a[x]=p; b[p]=y; d[p]=z;
		c[++p]=a[y]; a[y]=p; b[p]=x; d[p]=z;
	}
	bool bfs()
	{
		memset(h,0,sizeof h);
		for(h[dd[ll=rr=0]=t]=1;ll<=rr;ll++)
			for(int i=a[dd[ll]];i;i=c[i]) if (d[i^1]&&!h[b[i]])
				h[dd[++rr]=b[i]]=h[dd[ll]]+1;
		return h[s];
	}
	int dfs(int k,int now)
	{
		if (h[k]==1) return now;
		int tt=now;
		for(int i=a[k];i;i=c[i]) if (d[i]&&h[k]==1+h[b[i]])
		{
			int o=dfs(b[i],min(now,d[i]));
			now-=o; d[i]-=o; d[i^1]+=o;
			if (!now) break;
		}
		if (tt==now) h[k]=2000000000;
		return tt-now;
	}
	int maxflow()
	{
		int ret=0;
		for(;bfs();) ret+=dfs(s,inf);
		return ret;
	}
} a;
